package hl.alde;

public class Strassen {
    /*
     * m[i][j]表示Ai...Aj相乘最少的 计算次数
     * s[i][j]=k,表示在Ai...Aj中Ak位置切断，即这(j-i+1)个矩阵中最优子结构为Ai...Ak和A(k+1)...Aj
     * p[i]表示Ai的行数，p[i+1]表示Ai的列数
     */
    private int m[][];      // m表，存储 m[i:j]
    private int p[];		//
    private int s[][];		// s表，存储 k = s[i:j]

    public Strassen(){
        //this.p=new int[]{2,4,5,5,3};
        this.p=new int[]{3,5,2,4,3};    // 3*5 5*2 2*4 4*3 四个矩阵
        this.m=new int[4][4];       // 四个矩阵需要 4*4 的表
        this.s=new int[4][4];
    }

    public Strassen(int n,int []p){     // 定义 n 个矩阵，和 存储行列数的数组 p
        this.p=new int[n+1];
        this.m=new int[n][n];
        this.s=new int[n][n];
        for(int i=0;i<p.length;i++)
            this.p[i]=p[i];
    }
    /*********************方法一，动态规划**********************************/
    public void martixChain(){
        int n=m.length;	//取矩阵array行数
        for(int i=0;i<n;i++)//矩阵array对角线元素置0，m[i:i] = 0
            m[i][i]=0;

        for(int r=2;r<=n;r++)//r为链长：2表示Ai*Ai+1，需要计算A0*A1，A1*A2，A2*A3
        {
            for(int i=0;i<=n-r;i++)//r=2时，i取值0，1，2
            {
                int j=i+r-1;//??
                m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1];	//生成初次m表
                //System.out.printf("%8d",m[i][j]);
                s[i][j]=i;								//生成初次s表
                for(int k=i+1;k<j;k++)//i <= k < j      //更新ms表，取最小值
                {
                    int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
                    //System.out.printf("%8d=%d+%d+%d*%d*%d",t,m[i][k],m[k+1][j],p[i],p[k+1],p[j+1]);
                    if(t<m[i][j])
                    {
                        m[i][j]=t;
                        s[i][j]=k;
                    }
                }

            }
            System.out.println();
        }
    }
    /*
     * 如果待求矩阵为：Ap...Aq,then a=0,b=q-p
     */
    public void traceBack(int a,int b){
        /*
        if(a<b){
            traceBack(a, s[a][b]);
            traceBack(s[a][b]+1, b);
            System.out.println("先把A"+a+"到A"+s[a][b]+"括起来，在把A"+(s[a][b]+1)+"到A"+b+"括起来，然后把A"+a+"到A"+b+"括起来");
        }
         */
        if(a==b)System.out.print("A"+a);
        else
        {
            System.out.print("(");
            traceBack(a,s[a][b]);
            traceBack(s[a][b]+1,b);
            System.out.print(")");
        }
    }
    public void pr(){
        System.out.println();
        System.out.println("表 m :");
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m.length; j++)
                System.out.printf("%-8d" , m[i][j]);
            System.out.println();
        }
        System.out.println("表 s :");
        for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < s.length; j++)
                if (i>=j)
                    System.out.printf("%-8d" , s[i][j]);
                else
                    System.out.printf("%-8d" , s[i][j]);

            System.out.println();
        }
    }

    /*********************方法二：备忘录方法*****************************/
    public int memorizedMatrixChain(){
        int n=m.length;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++)
                m[i][j]=0;
        }
        return lookUpChain(0,n-1);
    }

    public int lookUpChain(int a,int b){
        if(m[a][b]!=0)
            return m[a][b];
        if(a==b)
            return 0;
        m[a][b]=lookUpChain(a, a)+lookUpChain(a+1, b)+p[a]*p[a+1]*p[b+1];
        s[a][b]=a;
        for(int k=a+1;k<b;k++){
            int t=lookUpChain(a, k)+lookUpChain(k+1, b)+p[a]*p[k+1]*p[b+1];
            if(t<m[a][b]){
                m[a][b]=t;
                s[a][b]=k;
            }
        }
        return m[a][b];
    }

    public static void main(String[] args) {
        //Strassen strassen=new Strassen();
        //strassen.martixChain();
        int[] p = new int[]{30,35,15,5,10,20,25};
        Strassen strassen=new Strassen(6,p);
        strassen.martixChain();
        //strassen.memorizedMatrixChain();
        strassen.traceBack(0, 5);
        strassen.pr();

    }
}















